public class t10_2dome {
    public static void main(String[] args) {
        String s = "aab";
        String p = "c*a*b";
        System.out.println(isMatch(s, p));


    }

    public static boolean isMatch(String s, String p) {
        if (p == null) {
            if (s == null) {
                return true;
            } else {
                return false;
            }
        }
        if (s == null && p.length() == 1) {
            return false;
        }
        int a = s.length() + 1;
        int b = p.length() + 1;
        boolean dp[][] = new boolean[a][b]; //表示到s[a]的p[b]能否匹配成功
        dp[0][0] = true;
        /**
         * 当s为空时候 或当p为空的时候的数组状态可以计算出来
         */
        for (int j = 2; j < b; j++) {//初始化数组
            if (p.charAt(j - 1) == '*') {//有*号也只能是下标为1及以后
                dp[0][j] = dp[0][j - 2];// #*匹配0次
            }
        }
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];//如果s[i] == p[j] || p[j] == . 则看前一种情况 dp[i][j] = dp[i-1][j-1];
                } else if (p.charAt(j - 1) == '*') {//如果p[j] == *  则
                    /*如果p[j-1] == s[i]
                        dp[i][j] = dp[i][j-2]; #*匹配0次
                        dp[i][j] = dp[i-1][j-1]; #* 匹配一次
                        dp[i][j] = dp[i-1][j]; #*匹配多次

                     */
                    if ((p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2] || dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i][j - 2];//匹配0次
                    }
                }
            }
        }


        return dp[a - 1][b - 1];
    }
}
